
"""
题目
基于单特征划分（ID3）的决策树进行二分类预测。给定一组无线网络质量的训练样本，每个样本有 m 个二值特征（取值 0/1）以及分类标签（0 表示正常，1 表示劣化）。信息熵定义为
H(S) = -∑ p_i · log2(p_i)，其中 p_i 为集合 S 中第 i 类样本占比。
按如下规则自根向下构建决策树：
每次在当前样本集合 S 上选择信息增益最大的特征划分；若增益并列，选索引更小的特征。
若 S 中所有样本标签相同，当前节点为叶子并返回该标签。
若无可用特征可继续划分，则将当前节点设为叶子，返回 S 中多数类（若 0/1 数量相同，返回 0）。
划分后若某个分支样本数为 0，则该分支直接为叶子，标签取父节点 S 的多数类（若 0/1 数量相同取 0）。
随后对 q 个查询样本进行分类预测。
输入
第一行：两个整数 n, m（训练样本数、特征数；2 ≤ m ≤ 10）。
接下来 n 行：每行包含 m 个特征值和 1 个标签，均为 0/1。输入既可能为用空格分隔的 m+1 个整数，也可能为紧凑形式的一个长度为 m+1 的 01 串（如 1011）。
下一行：一个整数 q（查询样本数）。
接下来 q 行：每行一个查询样本的 m 个特征值（同样支持空格分隔或紧凑 01 串）。
输出
输出 q 行，每行一个整数（0 或 1），对应每个查询样本的预测类别。
说明
采用信息增益（ID3）作为划分指标；熵与增益中的对数以 2 为底。
平局一律按“索引更小 / 多数类为 0”处理。
代码同时兼容“1011”与“1 0 1 1”的输入风格

"""

#核心方法：这是一道机器学习算法实现题，在LeetCode中属于树形数据结构 + 递归分治的范畴
# LeetCode中最接近的题目类型：
# 树形结构构建：类似 p297 二叉树的序列化与反序列化
# 递归分治：类似 p105 从前序与中序遍历序列构造二叉树
# 贪心选择：类似 p435 无重叠区间（每次选择最优策略）

# 这是典型的"贪心 + 递归"模式
# def build_tree(data):
#     if 终止条件:
#         return 叶子节点
    
#     # 贪心选择：当前最优特征
#     best_feat = 选择信息增益最大的特征()
    
#     # 递归分治：按特征值分割数据
#     left_data = 特征值=0的样本
#     right_data = 特征值=1的样本
    
#     return 节点(特征=best_feat, 
#                左子树=build_tree(left_data), 
#                右子树=build_tree(right_data))

import sys
import math



def parse_bits_line(s, length_expected):
    # 既支持空格分隔，也支持紧凑 01 串
    parts = s.split()
    if len(parts) == 1:
        bits = [int(c) for c in parts[0].strip()]
        if length_expected is not None and len(bits) != length_expected:
            raise ValueError("length mismatch")
        return bits
    else:
        nums = [int(x) for x in parts]
        if length_expected is not None and len(nums) != length_expected:
            raise ValueError("length mismatch")
        return nums

def entropy(cnt0, cnt1):
    n = cnt0 + cnt1
    if n == 0 or cnt0 == 0 or cnt1 == 0:
        return 0.0 if n > 0 else 0.0
    p0 = cnt0 / n
    p1 = cnt1 / n
    return -(p0 * math.log2(p0) + p1 * math.log2(p1))

def majority_label(labels):
    ones = sum(labels)
    zeros = len(labels) - ones
    return 1 if ones > zeros else 0  # 平局返回 0

class Node:
    __slots__ = ("is_leaf", "label", "feat", "child0", "child1")
    def __init__(self, is_leaf=False, label=None, feat=None, child0=None, child1=None):
        self.is_leaf = is_leaf
        self.label = label
        self.feat = feat
        self.child0 = child0
        self.child1 = child1

def build_id3(X, y, features):
    # 终止条件：纯
    if all(v == y[0] for v in y):
        return Node(is_leaf=True, label=y[0])

    # 无特征可用
    if not features:
        return Node(is_leaf=True, label=majority_label(y))

    n = len(y)
    cnt1 = sum(y)
    cnt0 = n - cnt1
    base_H = entropy(cnt0, cnt1)

    # 选信息增益最大的特征；并列取索引小
    best_feat = None
    best_gain = -1.0

    for f in features:
        idx0 = [i for i, row in enumerate(X) if row[f] == 0]
        idx1 = [i for i, row in enumerate(X) if row[f] == 1]

        y0 = [y[i] for i in idx0]
        y1 = [y[i] for i in idx1]

        H0 = entropy(len(y0) - sum(y0), sum(y0))
        H1 = entropy(len(y1) - sum(y1), sum(y1))
        weighted = (len(y0) / n) * H0 + (len(y1) / n) * H1
        gain = base_H - weighted

        if gain > best_gain or (abs(gain - best_gain) <= 1e-12 and (best_feat is None or f < best_feat)):
            best_gain = gain
            best_feat = f

    f = best_feat
    # 划分
    X0, y0 = [], []
    X1, y1 = [], []
    for row, label in zip(X, y):
        if row[f] == 0:
            X0.append(row)
            y0.append(label)
        else:
            X1.append(row)
            y1.append(label)

    # 子分支为空 → 直接设为父节点多数类
    maj = majority_label(y)
    next_features = [x for x in features if x != f]

    child0 = Node(is_leaf=True, label=maj) if len(y0) == 0 else build_id3(X0, y0, next_features)
    child1 = Node(is_leaf=True, label=maj) if len(y1) == 0 else build_id3(X1, y1, next_features)
    return Node(is_leaf=False, feat=f, child0=child0, child1=child1)

def predict_one(root, x):
    node = root
    while not node.is_leaf:
        node = node.child0 if x[node.feat] == 0 else node.child1
    return node.label

def main():
    
    n, m = map(int, input().split()) #改进成常见的acm方案成功
    X, y = [], []
    for _ in range(n):
        s = input().strip()
        bits = parse_bits_line(s, None)
        if len(bits) == m + 1:
            X.append(bits[:m])
            y.append(bits[m])
        elif len(bits) == m:
            # 若缺少标签则报错
            raise ValueError("training row must have m features + 1 label")
        else:
            # 紧凑串
            bits = parse_bits_line(s, m + 1)
            X.append(bits[:m])
            y.append(bits[m])

    q_line = input()
    q = int(q_line)
    Q = []
    for _ in range(q):
        s = input().strip()
        bits = parse_bits_line(s, None)
        if len(bits) == m:
            Q.append(bits)
        else:
            bits = parse_bits_line(s, m)
            Q.append(bits)

    root = build_id3(X, y, list(range(m)))
    out_lines = []
    for x in Q:
        out_lines.append(str(predict_one(root, x)))
    print("\n".join(out_lines))

if __name__ == "__main__":
    main()



"""
10 3
1 0 1 1
1 0 0 0
1 1 1 1
1 1 0 1
0 0 1 0
0 0 0 0
0 1 1 1
0 1 0 0
1 0 1 1
0 1 1 1
3
1 0 1
0 0 0
1 1 0

输出
1
0
1
"""

"""
6 2
1 1 1
0 0 0
1 0 1
0 1 0
1 1 1 
0 0 0
2
1 1
0 0

输出
1
0

"""


"""感受：不像是人写的东西，尤其是在输入输出上，和调用函数上"""
